Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій Кафедра “АСУ”
Лабораторна робота №8 Тема роботи: Керування мережним середовищем з допомогою утиліт Novell NetWare для DOS. Виконав: ст. гр. КН-3 Львів 2006 Мета роботи: Вивчення кодування та декодування інформації за допомогою циклічних кодів. Теоретичні відомості. Основна ідея CRC-алгоритмів. Проте в основі контрольної функції CRC-алгоритмів теж лежить арифметична операція - ділення. Послідовність біт вихідного повідомлення розглядається як величезне двійкове число, відбувається його цілочисельне ділення на фіксоване значення (твірний поліном), і залишок береться як контрольна сума. CRC(7,3) Ми можемо інтерпретувати обчислення CRC як узяття залишку від ділення. У цьому пункті ми обговоримо деякі деталі і розв’яжемо приклад. Розглянемо приклад CRC(7,3): CRC(7,3) означає що: загальна довжина послідовності n=7 біт довжина корисної інформації k=3 біта довжина надлишкової інформації r=n-k=7-3=4 біта (CRC- залишок) По-перше, необхідно вибрати твірний поліном. Його довжина повинна на один біт перевершувати необхідну довжину CRC. Тобто, для одержання CRC(7,3) необхідно взяти (n-k+1)=r+1=5-бітний поліном (дільник) (відповідно до даного вище визначення його довжина буде рівна 4). Оскільки залишок повинний бути менше дільника (інакше можна виконати ділення ще раз), ми одержимо CRC необхідної довжини. Узявши довільний дільник, ми прийдемо до деякого CRC-алгоритму. Однак не всі дільники дають гарні результати, тому треба з обережністю підходити до вибору. Дільник (твірний поліном) повинен відповідати таким вимогам: Степінь полінома повинна бути рівна r. Твірний поліном повинен бути неприводимий (ділитися тільки на себе). Поліном (x^n + 1) повинен ділитися на твірний поліном без остачі. 10000001|11101 11101 | 11010 | 11101 | 11101| 11101| 0| 10000001|10111 10111 | 11100 | 10111 | 10111| 10111| 0|  x^4+x^3+x^2+x^0 x^4+x^2+x^1+x^0  Для CRC(7,3) твірний поліном є 11101: x^4+x^3+x^2+x^0; треба зауважити, що поліном 10111 (дзеркальний до вибраного) також підійде, але будемо розглядати перший. Кодування На основі цього твірного полінома 11101 побудуємо схему кодера (ми будемо розглядати апаратне кодування) Вертикальні зв’язки в кодері будуються за таким принципом: Присутність і-го зв’язку на схемі відповідає присутності одинички при і-й степені у поліномі. 0 <= і <= n-k.
Пр.: 11101 (тв. поліном) і=0 ....1-> зв’язок зліва від a1 і=1 ...0.-> зв’язку нема зліва від a2 і=2 ..1..-> зв’язок зліва від a3 і=3 .1...-> зв’язок зліва від a4 і=4 1....-> останній зв’язок є. Треба зауважити, що перший та останній зв’язок є завжди. Нехай на вхід надходить k інформаційних біт тоді за k кроків у регістрах a1,a2,a3,a4 утвориться деяка послідовність яка і буде шуканим CRC. Розглянемо формули за якими можна аналітично визначити значення ai на кожному кроці. a1=a’4+k, a2=a’1, a3=k+a’4+a’2, a4=k+a’4+a’3, де a’I означає попередній стан I-го регістра (1<=I<=4). Оскільки a’4+k=a1 то формули для a3, a4 можна записати і так: a3=a1+a’2, a4=a1+a’3 Декодування
На основі твірного полінома будуємо схему декодера. Зв’язки у схемі будуються за тим самим принципом, що і у схемі кодера. Формули для визначення a1,a2,a3,a4 тепер будуть мати такий вигляд: a1=a’4+k, a2=a’1, a3=a’4+a’2, a4=a’4+a3 Декодер циклічного коду ділить прийняту кодову комбінацію на твірний поліном. Якщо у результаті в регістрах є лише нулі то має місце правильна передача або помилка що не виявляється. Розглянемо роботу декодера: У нашому випадку на вхід декодера поступає n=7 біт з них k=3 записуються у запам’ятовуючому регістрі. За n тактів (поки вона поступає) відбувається процес ділення на твірний поліном, якщо остача від ділення =0 то k біт з запам’ятовуючого регістру видаються користувачу.